/*!
 Temelia - Treap interface.

 Copyright (C) 2008, 2009 Ceata (http://cod.ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef TREAP_H_
#define TREAP_H_

#include "binary_tree_common.h"

struct _treap_node_t;
typedef struct _treap_node_t *treap_node_t;

/*!
 * @see binary_tree_new
 */
DECLSPEC treap_tree_t treap_tree_new(void *key);

/*!
 * @see binary_tree_delete_node
 */
DECLSPEC void treap_tree_delete_node(treap_tree_t treap);

/*!
 * @see binary_tree_delete
 */
DECLSPEC void treap_tree_delete(treap_tree_t treap);

/*!
 * @see binary_tree_compare_trees
 */
DECLSPEC char treap_tree_compare_trees(treap_tree_t treap1, treap_tree_t treap2,
		int (*compare)(void *x, void *y, void *context), void *context);

/*!
 * @see binary_tree_is_empty
 */
DECLSPEC char treap_tree_is_empty(treap_tree_t treap);

/*!
 * @see binary_tree_is_leaf
 */
DECLSPEC char treap_tree_is_leaf(treap_tree_t treap);

/*!
 * @see binary_tree_get_size
 */
DECLSPEC int treap_tree_get_size(treap_tree_t treap);

/*!
 * @see binary_tree_get_root
 */
DECLSPEC treap_tree_t treap_tree_get_root(treap_tree_t treap);

/*!
 * @see binary_tree_get_key
 */
DECLSPEC void *treap_tree_get_key(treap_tree_t treap);

/*!
 * @brief Returns the priority associated with tree's root.
 * Complexity O(1)
 *
 * @param Treap
 */
DECLSPEC unsigned int treap_tree_get_priority(treap_tree_t treap);

/*!
 * @see binary_tree_get_parent
 */
DECLSPEC treap_tree_t treap_tree_get_parent(treap_tree_t treap);

/*!
 * @see binary_tree_get_left_child
 */
DECLSPEC treap_tree_t treap_tree_get_left_child(treap_tree_t treap);

/*!
 * @see binary_tree_get_right_child
 */
DECLSPEC treap_tree_t treap_tree_get_right_child(treap_tree_t treap);

/*!
 * @see binary_tree_get_height
 */
DECLSPEC int treap_tree_get_height(treap_tree_t treap);

/*!
 * @see binary_tree_get_depth
 */
DECLSPEC int treap_tree_get_depth(treap_tree_t treap);

/*!
 * @see binary_search_tree_search
 */
DECLSPEC treap_tree_t treap_tree_search(treap_tree_t treap, void *key, int compare(void *x,
		void *y, void *context), void *context);

/*!
 * @see binary_search_tree_insert
 */
DECLSPEC treap_tree_t treap_tree_insert(treap_tree_t *treap, void *key, int compare(void *x,
		void *y, void *context), void *context, char adjust_root);

/*!
 * @see binary_search_tree_remove
 * Complexity O(log(n))
 *
 * @param Adjust root if user wants this. It's used when you remove the key
 * from the tree's root and keeping the same pointer you won't be able to see the
 * whole treap tree
 */
DECLSPEC treap_tree_t treap_tree_remove(treap_tree_t *treap, void *key, int compare(void *x,
		void *y, void *context), void *context, char adjust_root);

/*!
 * @see binary_search_tree_get_min
 */
DECLSPEC treap_tree_t treap_tree_get_min(treap_tree_t treap);

/*!
 * @see binary_search_tree_get_max
 */
DECLSPEC treap_tree_t treap_tree_get_max(treap_tree_t treap);

/*!
 * @see binary_tree_preorder
 */
DECLSPEC void treap_tree_preorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context);

/*!
 * @see binary_tree_inorder
 */
DECLSPEC void treap_tree_inorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context);

/*!
 * @see binary_tree_reverse_inorder
 */
DECLSPEC void treap_tree_reverse_inorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context);

/*!
 * @see binary_tree_postorder
 */
DECLSPEC void treap_tree_postorder(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context);

/*!
 * @see binary_tree_level_order
 */
DECLSPEC void treap_tree_level_order(treap_tree_t treap, void key_handler(void *x,
		void *context), void *context);

/*!
 * @see binary_tree_show_indented
 */
DECLSPEC void treap_tree_show_indented(treap_tree_t treap, void key_handler(void *x,
		int level, void *context), void *context);

#endif /* TREAP_H_ */
